#ifndef POLYGON_HPP
#define POLYGON_HPP
#include<vector>
#include <algorithm>
#include <cassert>
#include <iostream>
using namespace std;



class Point{
public:
    int x, y;
    Point() = default;
    Point(int a, int b): x(a), y(b) {}
    bool operator<(const Point &other) const {
        return (x < other.x) || (x == other.x && y < other.y);
    }
    bool operator==(const Point &other) const {
        return (x == other.x) && (y == other.y);
    }
    bool operator!=(const Point &other) const {
        return (x != other.x) || (y != other.y);
    }
    Point operator - (const Point &other) const {
        return {x - other.x, y - other.y};
    }
    Point operator + (const Point &other) const {
        return {x + other.x, y + other.y};
    }
    //叉积
    long long cross(const Point b) const{
        return 1ll * x * b.y - 1ll * y * b.x;
    }
    //点积
    long long dot(const Point b) const{
        return 1ll * x * b.x + 1ll * y * b.y;
    }
    //两点间曼哈顿距离
    int dis(const Point b) const{
        return abs(x - b.x) + abs(y - b.y);
    }
    int get_x() const {
        return x;
    }
    int get_y() const {
        return y;
    }
    Point rotate_nodes(int rot_type, int x_add, int y_add) const {
        int rotate_square[8][2][2] = {
                {{1, 0}, {0, 1}},
                {{0, 1}, {-1, 0}},
                {{-1, 0}, {0, -1}},
                {{0, -1}, {1, 0}},
                {{1, 0}, {0, -1}},
                {{0, 1}, {1, 0}},
                {{-1, 0}, {0, 1}},
                {{0, -1}, {-1, 0}}
        };
        return {x * rotate_square[rot_type][0][0] + y * rotate_square[rot_type][0][1] + x_add,
                     x * rotate_square[rot_type][1][0] + y * rotate_square[rot_type][1][1] + y_add};
    }
    //判断横线还是竖线
    //0：横线
    //1：竖线
    int get_line_type(Point other) const {
        if (x == other.x)
            return 1;
        return 0;
    }
    void printf() const {
        cout << "(" << x << "," << y << "),";
    }

    bool in_rectangle(int l, int r, int b, int t) const{
        return (x >= l && x <= r && y >= b && y <= t);
    }

    bool in_rectangle(Point a, Point b) const{
        return (x >= min(a.x, b.x)) && (x <= max(a.x, b.x)) && (y >= min(a.y, b.y)) && (y <= max(a.y, b.y));
    }

};

class Line{
    Point s{}, e{};
public:
    Line() = default;
    Line(Point x, Point y): s(x), e(y) { }
    Line(const Line & o) {
        s.x = o.s.x;
        s.y = o.s.y;
        e.x = o.e.x;
        e.y = o.e.y;
    }
    // 点是否在线段上
    bool on_line(Point a) const {
        return a.get_x() >= min(s.get_x(), e.get_x()) && a.get_x() <= max(s.get_x(), e.get_x()) && \
               a.get_y() >= min(s.get_y(), e.get_y()) && a.get_y() <= max(s.get_y(), e.get_y());
        // return (s - a).dot(e - a) <= 0;
    }

    static int sgn(long long x){
        if(x > 0) return 1;
        if(x < 0) return -1;
        return 0;
    }

    // 判断线段是否相交
    bool is_intersect(Line a){
        bool f1 = a.s.x == a.e.x, f2 = s.x == e.x;
        if(f1){
            if(f2){
                if(a.s.x != s.x) return false;
                return max(a.s.y, a.e.y) >= min(s.y, e.y) && min(a.s.y, a.e.y) <= max(s.y, e.y);
            }
            else{
                return max(s.x, e.x) >= a.s.x && min(s.x, e.x) <= a.s.x && max(a.s.y, a.e.y) >= s.y && min(a.s.y, a.e.y) <= s.y; 
            }
        }else{
            if(!f2){
                if(a.s.y != s.y) return false;
                return max(a.s.x, a.e.x) >= min(s.x, e.x) && min(a.s.x, a.e.x) <= max(s.x, e.x);
            }
            else{
                return max(s.y, e.y) >= a.s.y && min(s.y, e.y) <= a.s.y && max(a.s.x, a.e.x) >= s.x && min(a.s.x, a.e.x) <= s.x; 
            }
        }
        // if(sgn((s - e).cross(a.s - e)) * sgn((s - e).cross(a.e - e)) > 0) return false;
        // if(sgn((a.s - a.e).cross(s - a.e)) * sgn((a.s - a.e).cross(e - a.e)) > 0) return false;
        // return true;
    }

    // 找线段交点
    int get_intersect(Line a, Point *intersect){
        if (!is_intersect(a)) return 0;
        if ((e - s).cross(a.e - a.s) == 0) {//说明两条直线共线
            int ret = 0;
            if (on_line(a.s)) {
                intersect[ret].x = a.s.x;
                intersect[ret].y = a.s.y;
                ret++;
            }
            if(on_line(a.e)) {
                intersect[ret].x = a.e.x;
                intersect[ret].y = a.e.y;
                ret++;
            }
            if(a.on_line(s)) {
                intersect[ret].x = s.x;
                intersect[ret].y = s.y;
                ret++;
            }
            if(a.on_line(e)) {
                intersect[ret].x = e.x;
                intersect[ret].y = e.y;
                ret++;
            }
            sort(intersect, intersect + ret);
            ret = (int) (unique(intersect, intersect + ret) - intersect);
            return ret;
        } else {//说明两直线垂直
            int x[4], y[4];
            x[0] = e.x; x[1] = s.x;
            x[2] = a.e.x; x[3] = a.s.x;
            y[0] = e.y; y[1] = s.y;
            y[2] = a.e.y; y[3] = a.s.y;
            sort(x, x + 4); sort(y, y + 4);
            intersect[0].x = x[1];
            intersect[0].y = y[1];
            return 1;
        }
    }
};

class Polygon {
public:
    vector<Point> nodes; //存储为所有点相对于左下角的点的相对位置，第一个点为左下角的点，注意点的排序是不能交换相对位置的，只能旋转
    Point left_node; //存储为左下角的点的真实位置
    int left, right, top, bottom; //上下左右边界
    long long area; //面积
    vector<Point> move_nodes; //移动的点
    Point left_move_node; //移动的左下角点
    Point nb_node; //nb_polygon 的不动点
    int nb_id; // nb_polygon 不动点的下标
public:
    // Polygon 构造
    Polygon(): left(2e9), right(-2e9), top(-2e9), bottom(2e9), nb_id(0) {
        nodes.reserve(20);
    }

    Polygon(Polygon && o)  noexcept {
        nodes = move(o.nodes);
        left_node = o.left_node;
        left = o.left;
        right = o.right;
        top = o.top;
        bottom = o.bottom;
        area = o.area;
        move_nodes = move(o.move_nodes);
        left_move_node = o.left_move_node;
        nb_node = o.nb_node;
        nb_id = o.nb_id;
    }

    Polygon(const Polygon & o)  noexcept {
        nodes = o.nodes;
        left_node = o.left_node;
        left = o.left;
        right = o.right;
        top = o.top;
        bottom = o.bottom;
        area = o.area;
        move_nodes = o.move_nodes;
        left_move_node = o.left_move_node;
        nb_node = o.nb_node;
        nb_id = o.nb_id;
    }

    Polygon & operator=(const Polygon & o)  noexcept = default;

    void add_node(Point p) {
        nodes.emplace_back(p);
    }

    void add_move_node(Point p) {
        move_nodes.emplace_back(p);
    }

    void merge(Polygon poly){
        int id;

        for(id = 0; id < nodes.size(); id++){
            if(nodes[id] == Point(0, 0)){
                left_move_node = poly.get_node(id) + poly.get_left_node();
                break;
            }
        }
        for (int i = id; i < poly.get_node_size(); i++) {
            move_nodes.emplace_back(poly.get_node(i) + poly.get_left_node() - left_move_node);
        }
        for (int i = 0; i < id; i++) {
            move_nodes.emplace_back(poly.get_node(i) + poly.get_left_node() - left_move_node);
        }
        for (int i = 0; i < poly.get_node_size(); i++){
            left = min(left, (poly.get_node(i) + poly.get_left_node()).get_x());
            right = max(right, (poly.get_node(i) + poly.get_left_node()).get_x());
            top = max(top, (poly.get_node(i) + poly.get_left_node()).get_y());
            bottom = min(bottom, (poly.get_node(i) + poly.get_left_node()).get_y());
        }
        init_static_node();
    }

    //找出左下角点，并按照左下角点排序
    void sort_nodes() {
        vector<Point> tmp;
        //深拷贝nodes
        tmp.swap(nodes);
        left_node = tmp[0];
        int start = 0;
        int sz = tmp.size();
        for (int i = 1; i < sz; i++) {
            if (tmp[i] < left_node) {
                left_node = tmp[i];
                start = i;
            }
        }
        nodes.reserve(sz);
        for (int i = start; i < sz; i++) {
            nodes.push_back(tmp[i] - left_node);
        }
        for (int i = 0; i < start; i++) {
            nodes.push_back(tmp[i] - left_node);
        }
        for (auto const &node: tmp){
            left = min(left, node.get_x());
            right = max(right, node.get_x());
            top = max(top, node.get_y());
            bottom = min(bottom, node.get_y());
        }
        if(!move_nodes.empty()){
            tmp.clear();
            tmp.swap(move_nodes);
            left_move_node = tmp[start];
            sz = (int) tmp.size();
            move_nodes.reserve(sz);
            for (int i = start; i < sz; i++) {
                move_nodes.push_back(tmp[i] - left_move_node);
            }
            for (int i = 0; i < start; i++) {
                move_nodes.push_back(tmp[i] - left_move_node);
            }
            for (auto &node: tmp){
                left = min(left, node.get_x());
                right = max(right, node.get_x());
                top = max(top, node.get_y());
                bottom = min(bottom, node.get_y());
            }
        }
    }

    //判断两个多边形形状相同
    int move_equal (Polygon& other) {
        if(!get_move_node_size() && !other.get_move_node_size()){
            if (nodes.size() != other.get_node_size())
                return -1;
            if (area != other.get_area())
                return -1;
            for (int i = 0; i < nodes.size(); i++)
                if (nodes[i] != other.get_node(i))
                    return -1;
            return 0;
        }
        else if(get_move_node_size()){
            if (nodes.size() != other.get_node_size())
                return -1;
            int num = nodes.size();
            for (int bias = 0; bias < num; bias++){
                Point diff = nb_node + left_node - other.get_node(bias) - other.get_left_node();
                bool f = true;
                for (int cnt = 0, i = nb_id, j = bias; cnt < num; i++, j++, cnt++){
                    if(j == num) j = 0;
                    if(i == num) i = 0;
                    if (!(other.get_node(j) + other.get_left_node() + diff).in_rectangle(nodes[i] + left_node, move_nodes[i] + left_move_node)){
                        f = false;
                        break;
                    }
                }
                if(f) return bias;
            }
            return -1;
        }
        else{
            if (nodes.size() != other.get_node_size())
                return -1;
            int num = nodes.size();
            for (int bias = 0; bias < num; bias++){
                Point diff = other.get_static_node() + other.get_left_node() - get_node(bias) - left_node;
                bool f = true;
                for (int cnt = 0, i = other.get_static_node_id(), j = bias; cnt < num; i++, j++, cnt++){
                    if(j == num) j = 0;
                    if(i == num) i = 0;
                    if (!(nodes[j] + left_node + diff).in_rectangle(other.nodes[i] + other.get_left_node(), other.move_nodes[i] + other.get_left_move_node())){
                        f = false;
                        break;
                    }
                }
                if(f) return bias;
            }
            return -1;
        }
    }

    // bool 等于：判断两个多边形相等且相对位置相同
    bool operator==(Polygon &other) const {
        if(!get_move_node_size() && !other.get_move_node_size()){
            if (left_node != other.get_left_node())
                return false;
            if (nodes.size() != other.get_node_size())
                return false;
            if (area != other.get_area())
                return false;
            for (int i = 0; i < nodes.size(); i++)
                if (nodes[i] != other.get_node(i))
                    return false;
            return true;
        }
        else if(get_move_node_size()){
            if (nodes.size() != other.get_node_size())
                return false;
            int num = nodes.size();
            for (int bias = 0; bias < num; bias++){
                bool f = true;
                for (int i = 0, j = bias; i < num; i++, j++){
                    if (j == num) j = 0;
                    if (!(other.get_node(j) + other.get_left_node()).in_rectangle(nodes[i] + left_node, move_nodes[i] + left_move_node))
                        f = false;
                }
                if(f) return true;
            }
            return false;
        }
        else{
            if (nodes.size() != other.get_node_size())
                return false;
            int num = nodes.size();
            for (int bias = 0; bias < num; bias++){
                bool f = true;
                for (int i = 0, j = bias; i < num; i++, j++){
                    if (j == num) j = 0;
                    if (!(nodes[j] + left_node).in_rectangle(other.get_node(i) + other.get_left_node(), other.get_move_node(i) + other.get_left_move_node()))
                        f = false;
                }
                if(f) return true;
            }
            return false;
        }
    }

    // bool 不等于：判断两个多边形相等
    bool operator!=(Polygon &other) const {
        return !(*this == other);
    }

    //bool 重载小于号
    // 用于pattern内的排序
    // 由于图形没有重叠，因而不会出现left_node相等的情况
    bool operator<(const Polygon &other) const {
        return (left_node < other.left_node);
    }

    // bool 判断多边形是否在矩形内

    // Vector<Polygon> 求矩形与多边形的交
    vector<Polygon> get_conflict_polygons(int l, int r, int b, int t) {
        //TODO: 目前未处理切割线与边重合的情况
        vector<Polygon> ps;
        if(top <= t && bottom >= b && left >= l && right <= r) {
            ps.push_back(*this);
            return ps;
        }
        vector<Line> edge;
        edge.emplace_back(Line(Point(l, b), Point(r, b)));
        edge.emplace_back(Line(Point(r, b), Point(r, t)));
        edge.emplace_back(Line(Point(r, t), Point(l, t)));
        edge.emplace_back(Line(Point(l, t), Point(l, b)));
        vector<Point> tmp_node;
        Point intersect[4];
        for(int i = 0, j = 1; i < nodes.size(); i++, j++){
            if(j == nodes.size()) j = 0;
            Line cur = Line((nodes[i] + left_node), (nodes[j] + left_node));
            if((nodes[i] + left_node).in_rectangle(l, r, b, t)){
                tmp_node.emplace_back(nodes[i] + left_node);
            }
            for(auto &line: edge){
                int num = cur.get_intersect(line, intersect);
                if (num >= 1) {
                    tmp_node.push_back(intersect[0]);
                    if (num == 2) {
                        tmp_node.push_back(intersect[1]);
                    }
                }
            }
        }
        Polygon poly;
        for(auto node: tmp_node){
            if(poly.get_node_size() && poly.get_node(poly.get_node_size() - 1) != node)
                poly.add_node(node);
            else if(!poly.get_node_size())
                poly.add_node(node);
        }
        if(poly.get_node_size()){
            poly.init_area();
            poly.sort_nodes();
            ps = poly.split_poly();
        }
        return ps;
    }

    static int point_on_curve(Point pt, vector<Point> &a){
        if(a.size() <= 1) return -1;
        for(int id = 0; id + 1 < a.size(); id++){
            if(Line(a[id], a[id + 1]).on_line(pt)) return id;
        }
        return -1;
    }

    static int line_on_curve(Line line, vector<Point> &a){
        for(int id = 0; id + 2 < a.size(); id++){
            if(line.on_line(a[id])) return id;
        }
        return -1;
    }

    //将一个polygon拆分成多个简单的polygon
    vector<Polygon> split_poly(){
        vector<Polygon> res;
        vector<Point> current_poly;
        for(auto node: nodes){
            int intersect_id = point_on_curve((node + left_node), current_poly);
            current_poly.emplace_back(node + left_node);
            if(intersect_id != -1){
                Polygon tmp;
                for(int _ = intersect_id + 1; _ < current_poly.size(); _++){
                    tmp.add_node(current_poly[_]);
                }
                while(current_poly.size() > intersect_id + 1)
                    current_poly.pop_back();
                tmp.init_area();
                tmp.sort_nodes();
                res.emplace_back(tmp);
            } else if(current_poly.size() >= 2){
                intersect_id = line_on_curve(Line(current_poly[current_poly.size() - 1], current_poly[current_poly.size() - 2]), current_poly);
                // std::printf("%d\n", intersect_id);
                if(intersect_id != -1){
                    vector<Point> node;
                    for(int _ = intersect_id + 1; _ < current_poly.size(); _++){
                        node.emplace_back(current_poly[_]);
                    }
                    while(current_poly.size() > intersect_id + 1)
                        current_poly.pop_back();
                    current_poly.emplace_back(node.back());
                    node.pop_back();
                    Polygon tmp;
                    for(auto &x: node){
                        tmp.add_node(x);
                    }
                    tmp.init_area();
                    tmp.sort_nodes();
                    res.emplace_back(tmp);
                } 
            }
        }
        if(!current_poly.empty()){
            Polygon tmp;
            for(auto &node: current_poly)
                tmp.add_node(node);
            tmp.init_area();
            tmp.sort_nodes();
            res.emplace_back(tmp);
        }
        return res;
    }

    // 多边形初始化面积
    void init_area(){
        area = 0;
        for(int i = 0, j = 1; i < nodes.size(); i++, j++){
            if(j == nodes.size()) j = 0;
            area += nodes[i].cross(nodes[j]);
        }
        area = abs(area) / 2;
    }

    void reverse_nodes() {
        reverse(nodes.begin(), nodes.end());
    }

    void reverse_move_nodes() {
        reverse(move_nodes.begin(), move_nodes.end());
    }

    Polygon polygon_rotate(int rotate_type, int x_add, int y_add) {
        Polygon p;
        for (auto & node : nodes) {
            p.add_node((left_node + node).rotate_nodes(rotate_type, x_add, y_add));
        }
        for (auto & move_node : move_nodes) {
            p.add_move_node((left_move_node + move_node).rotate_nodes(rotate_type, x_add, y_add));
        }
        //镜像时点的顺序需要反过来
        if (rotate_type >= 4)
            p.reverse_nodes(), p.reverse_move_nodes();
        p.init_area();
        p.sort_nodes();

        if(p.get_move_node_size())
            p.init_static_node();
        return p;
    }

    bool judge_conflict_square(int l, int r, int b, int t) const {
        if (r < left || l > right || t < bottom || b > top)
            return false;
        return true;
    }

    bool is_inside(int width, int height) const{
        return left > 0 && right < width && bottom > 0 && top < height;
    }


    bool has_static_node(){
        if(!get_move_node_size())
            return true;
        int num = get_move_node_size();
        for(int i = 0; i < num; i++){
            if(left_node + get_node(i) == left_move_node + get_move_node(i)){
                return true;
            }
        }
        return false;
    }

    int init_static_node_id(){
        if(!get_move_node_size())
            return 0;
        int num = get_move_node_size();
        for(int i = 0; i < num; i++){
            if(left_node + get_node(i) == left_move_node + get_move_node(i)){
                return i;
            }
        }
        return 0;
    }

    int get_static_node_id(){
        return nb_id;
    }

    void init_static_node(){
        nb_id = init_static_node_id();
        nb_node = nodes[nb_id];
    }

    Point get_static_node(){
        return nb_node;
    }

    Point get_left_node() {
        return left_node;
    }

    Point get_left_move_node(){
        return left_move_node;
    }

    int get_node_size() const {
        return nodes.size();
    }

    int get_move_node_size() const{
        return move_nodes.size();
    }

    Point get_node(int i) {
        return nodes[i];
    }

    Point get_move_node(int i) {
        return move_nodes[i];
    }

    void set_node(int i, Point point){
        nodes[i] = point;
    }

    void set_left_node(Point point){
        left_node = point;
    }

    long long get_area() const{
        return area;
    }

    int get_bottom() const{
        return bottom;
    }

    int get_top() const{
        return top;
    }

    int get_left() const{
        return left;
    }

    int get_right() const{
        return right;
    }

    void printf() {
        for (auto & node : nodes) {
            Point n = node + left_node;
            n.printf();
        }
        cout << endl;
        if(!move_nodes.empty()){
            cout << "[";
            for (auto & move_node : move_nodes) {
                Point n = move_node + left_move_node;
                n.printf();
            }
            cout << "]" << endl;
        }
    }


};


struct MiniPolygon {
    int left, right, top, bottom;

    MiniPolygon(int left, int right, int top, int bottom):
            left(left), right(right), top(top), bottom(bottom) {}

    bool judge_conflict_square(int l, int r, int b, int t) const {
        if (r < left || l > right || t < bottom || b > top)
            return false;
        return true;
    }
};

#endif